/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/contains-duplicate-iii
   @Language: C++
   @Datetime: 19-05-27 11:14
   */

// Method 1, sort
class Solution {
	static bool compair(const pair<int,int> &a, const pair<int,int> &b){
		if(a.first==b.first) return a.second<b.second;
		return a.first<b.first;
	}
public:
	/**
	 * @param nums: the given array
	 * @param k: the given k
	 * @param t: the given t
	 * @return: whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
	 */
	bool containsNearbyAlmostDuplicate(vector<int> &nums, int k, int t) {
		// Write your code here
		vector<pair<int,int> > vp(nums.size());	// num,index
		for(int i=nums.size(); i--; vp[i]=make_pair(nums[i],i));
		sort(vp.begin(),vp.end(),compair);
		for(int i=0; i<vp.size(); ++i){
			for(int j=i+1; j<vp.size() && vp[j].first-vp[i].first<=t; ++j){
				if(abs(vp[j].second-vp[i].second)<=k) return true;
			}
		}
		return false;
	}
};

// Method 2, slide window + set
class Solution {
public:
	/**
	 * @param nums: the given array
	 * @param k: the given k
	 * @param t: the given t
	 * @return: whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
	 */
	bool containsNearbyAlmostDuplicate(vector<int> &nums, int k, int t) {
		// Write your code here
		multiset<int> win;
		for(int i=0; i<nums.size(); win.insert(nums[i++])){
			if (i>k) win.erase(win.find(nums[i-k-1]));
			auto low=win.lower_bound(nums[i]);
			if (low!=win.end() && 0L+*low-nums[i]<=t) return true;
			if (low!=win.begin() && 0L+nums[i]-*--low<=t) return true;
		}
		return false;
	}
};
